package week3;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 22. 括号生成
 * https://leetcode-cn.com/problems/generate-parentheses/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了85.41% 的用户
 * 内存消耗：38.7 MB, 在所有 Java 提交中击败了29.79% 的用户
 *
 *
 */
public class Week3GenerateParentheses {

    public List<String> generateParenthesis(int n) {
        List<String> parenthesisList = new ArrayList<String>();
        if(n == 0 ) {
            return parenthesisList;
        }
        dfs("", 0, 0, n, parenthesisList);
        return parenthesisList;
    }

    public void dfs(String currentString, int left, int right, int n, List<String> list) {
        if(left == n && right == n) {
            // 终止
            list.add(currentString);
            return;
        }
        if (left < right) {
            // 终止
            return;
        }
        if(left < n) {
            // 添加左括号
            dfs(currentString + "(", left + 1, right, n, list);
        }
        if(right < n) {
            // 添加右括号
            dfs(currentString + ")", left, right + 1, n, list);
        }
    }

}
